////https://www.luogu.com.cn/problem/P1379
//
//#include<algorithm>
//#include<iostream>
//#include<queue>
//#include<string>
//#include<unordered_map>
//using namespace std;
//
//string s;
//queue<string> q;
//unordered_map<string, int> map;
//int dx[] = { 0,0,1,-1 };
//int dy[] = { 1,-1,0,0 };
//string target = "123804765";
//
//int bfs()
//{
//	if (s == target) return 0;
//	q.push(s);
//	map[s] = 0;
//	while (!q.empty())
//	{
//		string ts = q.front();
//		q.pop();
//		int pos = 0;
//		while (ts[pos] != '0') pos++;
//		int x = pos / 3, y = pos % 3;
//		for (int i = 0; i < 4; i++)
//		{
//			string t = ts;
//			int nx = x + dx[i], ny = y + dy[i];
//			if (nx >= 3 || nx < 0 || ny >= 3 || ny < 0) continue;
//			int npos = nx * 3 + ny;
//			swap(t[pos], t[npos]);
//			if (map[t]) continue;
//			map[t] = map[ts] + 1;
//			if (t == target) return map[t];
//			q.push(t);
//		}
//	}
//	return -1;
//}
//
//int main()
//{
//	cin >> s;
//	cout << bfs();
//	return 0;
//}